729C - Road to Cinema - CodeForces Solution

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(x) x.begin(), x.end()
#define push(x) push_back(x)
#define fill(arr, val) memset(arr, val, sizeof(arr));
#define forto(i, a, b) for (int i = a; i <= b; i++)
#define fordw(i, b, a) for (int i = b; i >= a; i--)
#define ll long long
#define price first
#define futank second
#define S (gas[i] - gas[i-1])

using namespace std;

int main()
{
    IOS

    ll n, k, s, t; cin >> n >> k >> s >> t;

    vector<pair<ll, ll>> car(n);
    vector<ll> gas(k+2); gas[0] = 0; gas[k+1] = s;

    for (int i = 0; i < n; i++)
    {
        cin >> car[i].price >> car[i].futank;
    }

    for (int i = 1; i <= k; i++)
    {
        cin >> gas[i];
    }

    sort(all(gas));
    
    ll l = 0, r = (int)1e9;
    ll ans;

    while (l <= r)
    {
        ll m = (l+r)/2;

        bool check = true;

        ll sumT = 0;

        for (int i = 1; i < gas.size(); i++)
        {
            if (m - S < 0)
            {
                check = false;
                break;
            }
            else sumT += 2*S - min(m-S, S);
        }
        if (!check || sumT > t)
        {
            l = m + 1;
        }
        else
        {
            ans = m;
            r = m -1;
        }
    }

    ll mmb = LLONG_MAX;

    for (int i = 0; i < n; i++)
    { 
        if (car[i].futank >= ans)
        {
            mmb = min(car[i].price, mmb);
        }
    }

    cout << (mmb != LLONG_MAX ? mmb : -1);

    return 0;
}